#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int i = 0;
//	for (i = 30; i >= 0;i -= 2)
//	{
//		printf("%d", ((n >> i) & 1));
//	}
//	printf("\n");
//	for (i = 31; i >= 1; i -= 2)
//	{
//		printf("%d", ((n >> i) & 1));
//	}
//	return 0;
//}

//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int arr[20];
//	int i = 0;
//	while (n)
//	{
//		arr[i] = n % 6;
//		n = n / 6;
//		i++;
//	}
//	for (--i; i >= 0; i--)
//	{
//		printf("%d", arr[i]);
//	}
//	return 0;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int i = 0;
//	int j = 0;
//	int arr[n];
//	for (i = 0; i<n; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	int del = 0;
//	scanf("%d", &del);
//	for (i = 0; i<n; i++)
//	{
//		if (arr[i] != del)
//		{
//			arr[j] = arr[i];
//			j++;
//		}
//	}
//	for (i = 0; i<j; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	return 0;
//}

//
//int main()
//{
//	long n = 0, m = 0;
//	scanf("%d %d", &n, &m);
//	long r = 0;
//	long m2 = m;
//	long n2 = n;
//	while (r = n%m)
//	{
//		n = m;
//		m = r;
//	}
//	printf("%ld", m2*n2 / m + m);
//	return 0;
//}

//int walk(int n)
//{
//	if (n <= 2)
//		return n;
//	if (n>2)
//		return walk(n - 2) + walk(n - 1);
//}
//int main()
//{
//	int i = 0;
//	scanf("%d", &i);
//	int ret = walk(i);
//	printf("%d\n", ret);
//	return 0;
//}

//int walk(int i)
//{
//	if (i <= 2)
//		return i;
//	else
//		return walk(i - 1) + walk(i - 2);
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = walk(n);
//	printf("%d\n", ret);
//	return 0;
//}

//int main()
//{
//	int i = 0;
//	int j=0;
//	for (i = 1; i <=9; i++)
//	{
//		for (j = 1; j <=i; j++)
//		{
//			printf("%d*%d=%d ", i, j, i*j);
//		}
//		printf("\n");
//	}
//	return 0;
//}
//
//int year(int i)
//{
//	if (((i % 4 == 0) && (i % 100 != 0)) || (i % 400 == 0))
//		return 1;
//	else
//		return 0;
//}
//
//
//int main()
//{
//	int i = 0;
//	scanf("%d", &i);
//	int ret=year(i);
//	if (ret == 1)
//		printf("YES");
//	else
//		printf("NO");
//	return 0;
//}


//void my_strcpy(int* a,int* b)
//{
//	int tmp = 0;
//	tmp = *a;
//	*a = *b;
//	*b = tmp;
//}
//
//int main()
//{
//	int a = 0;
//	int b = 0;
//	scanf("%d %d", &a, &b);
//	my_strcpy(&a,&b);
//	printf("%d,%d", a, b);
//	return 0;
//}

//#include<math.h>
//#include<stdio.h>
//int main()
//{
//	int i = 0;
//	int j = 0;
//	int count = 0;
//	for (i = 100; i <= 200; i++)
//	{
//		int flag = 1;
//		for (j = 2; j <= sqrt(i); j++)
//		{
//			if (i%j == 0)
//			{
//				flag = 0;
//				break;
//			}
//		}
//		if (1 == flag)
//		{
//			count++;
//			printf("%d ", i);
//		}
//	}
//	printf("\ncount=%d", count);
//	return 0;
//}